package leetcode.剑指offer.前40;

import leetcode.剑指offer.pojo.TreeNode;
import org.junit.Test;

import java.util.*;

/**
 * @author :songyaozhang
 * @date :Created 2021/7/30 10:16
 * @description :
 */
public class 剑指_34_二叉树中和为某一值的路径 {
    @Test
    public void test() {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(5, new TreeNode(4,
                new TreeNode(11, new TreeNode(7, null, null), new TreeNode(2, null, null)), null),
                new TreeNode(8, new TreeNode(13), new TreeNode(4, new TreeNode(5), new TreeNode(1))));
        // TreeNode root = new TreeNode(-2, null, new TreeNode(-3));
        System.out.println(solution.pathSum(root, 22));
    }

    class Solution {
        List<List<Integer>> ans = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            dfs(root, target);
            return ans;
        }

        private void dfs(TreeNode node, int target) {
            if (node == null) return;
            path.offerLast(node.val);
            target -= node.val;
            if (target == 0 && node.left == null && node.right == null) {
                ans.add(new LinkedList<>(path));
            }
            dfs(node.left, target);
            dfs(node.right, target);
            path.pollLast();
        }
    }

    /*
    class Solution {
        List<List<Integer>> ans = new ArrayList<>();
        int target;
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            if (root == null) return ans;
            this.target = target;
            dfs(root, new ArrayList<>(), 0);
            return ans;
        }
        private void dfs(TreeNode node, ArrayList<Integer> list, int sum) {
            ArrayList<Integer> curList = new ArrayList<>(list);
            curList.add(node.val);
            sum += node.val;
            if (sum == target && node.left == null && node.right == null) {
                ans.add(curList);
                System.out.println(curList);
                return;
            }
            if (node.left != null) {
                dfs(node.left, curList, sum);
            }
            if (node.right != null) {
                dfs(node.right, curList, sum);
            }
        }
    }
     */

    /*class Solution {
        private List<List<Integer>> ans = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            dfs(root, target);
            return ans;
        }

        private void dfs(TreeNode node, int target) {
            if (node == null) return;
            path.offerLast(node.val);
            target -= node.val;
            if (target == 0 && node.left == null && node.right == null) {
                ans.add(new LinkedList<>(path));
            }
            dfs(node.left, target);
            dfs(node.right, target);
            path.pollLast();
        }
    }*/

    //bfs
    /*class Solution {
        private List<List<Integer>> ans = new ArrayList<>();
        private Map<TreeNode, TreeNode> map = new HashMap<>();
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            if (root == null) return ans;
            Queue<TreeNode> queueNode = new LinkedList<>();
            Queue<Integer> queueSum = new LinkedList<>();
            queueNode.offer(root);
            queueSum.offer(0);
            while (!queueNode.isEmpty()) {
                TreeNode cur = queueNode.poll();
                int sum = queueSum.poll() + cur.val;
                if (cur.left == null && cur.right == null) {
                    if (sum == target) {
                        getPath(cur);
                    }
                } else {
                    if (cur.left != null) {
                        map.put(cur.left, cur);
                        queueNode.offer(cur.left);
                        queueSum.offer(sum);
                    }
                    if (cur.right != null) {
                        map.put(cur.right, cur);
                        queueNode.offer(cur.right);
                        queueSum.offer(sum);
                    }
                }
            }
            return ans;
        }

        private void getPath(TreeNode node) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(node.val);
            while (map.get(node) != null) {
                node = map.get(node);
                list.add(node.val);
            }
            Collections.reverse(list);
            ans.add(list);
        }
    }*/
}

